/*
sample input:
5
a 1 b 1 c 4 d 5 e 14
*/

#include <iostream>
#include <queue>
#include <ranges>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;

struct Node {
    unordered_set<char> chars;
    double weight;

    partial_ordering operator<=>(const Node &other) const {
        return weight <=> other.weight;
    }

    Node merge(Node &other) {
        chars.merge(other.chars);
        weight += other.weight;
        return *this;
    }
};


int main() {
    unordered_map<char, vector<int> > codes;
    priority_queue<Node, vector<Node>, greater<> > pq;

    int n;
    cin >> n;

    for (int i = 0; i < n; i++) {
        char ch;
        double weight;
        cin >> ch >> weight;
        pq.emplace(unordered_set{ch}, weight);
    }

    while (pq.size() > 1) {
        Node left = pq.top();
        pq.pop();
        Node right = pq.top();
        pq.pop();

        for (const char &ch: left.chars)
            codes[ch].emplace_back(0);
        for (const char &ch: right.chars)
            codes[ch].emplace_back(1);
        Node parent = left.merge(right);
        pq.push(parent);
    }

    for (const auto &[ch, code]: codes) {
        cout << ch << ":";
        for (const int &bit: code | views::reverse)
            cout << bit;
        cout << endl;
    }

    return 0;
}

